package hackerrank.algorithms.warmup;

import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

/**
 * Created by Tzachi on 16/10/2014.
 * <p>
 * Bigger is Greater
 * Given a word w, rearrange the letters of w to construct another word s in such a way that,
 * s is lexicographically greater than w. In case of multiple possible answers,
 * find the lexicographically smallest one.
 */
public class NextStringPermutation {

    private static final String NO_ANSWER = "no answer";

    public static String getNextPermotation(String string) {
        /*Find the largest index k such that a[k] < a[k + 1]. If no such index exists,
         the permutation is the last permutation
        */
        char[] input = string.toCharArray();
        int k = -1;
        for (int i = 0; i <= input.length - 2; i++) {
            if (input[i] < input[i + 1]) {
                k = i;
            }
        }
        if (k == -1) {
            return NO_ANSWER;
        }

        /*
        Find the largest index l greater than k such that a[k] < a[l].
         */
        int l = -1;
        for (int i = k + 1; i <= input.length - 1; i++) {
            if (input[k] < input[i]) {
                l = i;
            }
        }
        /*
           Swap the value of a[k] with that of a[l]
         */
        char tmp = input[k];
        input[k] = input[l];
        input[l] = tmp;

        // Reverse the sequence from a[k + 1] up to and including the final element a[n]
        int startSwap = k + 1;
        int numberOfSwaps = (input.length - (k + 1)) / 2;
        for (int i = 0; i < numberOfSwaps; i++) {
            char tmp2 = input[startSwap + i];
            input[startSwap + i] = input[input.length - i - 1];
            input[input.length - i - 1] = tmp2;
        }

        return new String(input);
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // N & T
        int numberOfTestCases = in.nextInt();
        List<String> testCases = new LinkedList<>();
        for (int i = 0; i < numberOfTestCases; i++) {
            testCases.add(in.next());
        }

        //start checking
        for (String testCase : testCases) {
            System.out.println(getNextPermotation(testCase));
        }
    }
}
